/*
 *  map.cpp
 *  
 *  Created by Brian Bilbo on 12/03/09.
 *
 */

#include "map.h"
#include <vector>
#include <cstdlib> 
#include <ctime>
#include <iostream>
#include "DJ.CPP"
#include <algorithm>

#include <fstream>
using namespace std;

#define MAP_ROWS 10
#define MAP_COLS 10
#define MAP_EDGES 163

int Map::numberOfRows = MAP_ROWS;
int Map::numberOfCols = MAP_COLS;

Map::Map() {
	for (int row = 0; row < numberOfRows; row++) {
		for (int col = 0; col < numberOfCols; col++) {
			nodes[row][col] = new Node(row, col);
		}
	}
	
	std::vector<Node*> nodesWithEdges;
	std::vector<Node*> nodesWithNoFreeEdges;
	
	for (int ii = 0; ii < MAP_EDGES; ii++) {
		edges[ii] = new Edge();
		
		if (!USEEXISTINGMAP) {
			if (nodesWithEdges.size() == 0) {
				int nodeRow = MAP_ROWS/2-1;
				int nodeCol = MAP_COLS/2-1;
				Node* node1 = nodes[nodeRow][nodeCol];
				Node* node2 = NULL;
				
				edges[ii]->node1 = node1;
				nodesWithEdges.push_back(node1);
				
				srand((unsigned)time(0));
				int random_integer = (rand()%4)+1;
				switch (random_integer) {
					case 1:
						// try the top node
						node2 = nodes[node1->row-1][node1->col];
						edges[ii]->node2 = node2;
						nodesWithEdges.push_back(node2);
						
						node1->northEdge = edges[ii];
						node2->southEdge = edges[ii];
						break;
					case 2:
						// try the left node
						node2 = nodes[nodeRow][nodeCol-1];
						edges[ii]->node2 = node2;
						nodesWithEdges.push_back(node2);
						
						node1->westEdge = edges[ii];
						node2->eastEdge = edges[ii];
						break;
					case 3:
						// try the bottom node
						node2 = nodes[nodeRow+1][nodeCol];
						edges[ii]->node2 = node2;
						nodesWithEdges.push_back(node2);
						
						node1->southEdge = edges[ii];
						node2->northEdge = edges[ii];
						break;
					case 4:
						// try the right node
						node2 = nodes[nodeRow][nodeCol+1];
						edges[ii]->node2 = node2;
						nodesWithEdges.push_back(node2);
						
						node1->eastEdge = edges[ii];
						node2->westEdge = edges[ii];
						break;
					default:
						node2 = nodes[nodeRow][nodeCol+1];
						edges[ii]->node2 = node2;
						nodesWithEdges.push_back(node2);
						
						node1->eastEdge = edges[ii];
						node2->westEdge = edges[ii];
				}
			} else {
				bool pickedTwoNodes = false;
				while (!pickedTwoNodes) {
					srand((unsigned)time(0));
					int random_integer = (rand()%nodesWithEdges.size())+1;
					Node* node1 = nodesWithEdges[random_integer - 1];
					Node* node2 = NULL;
					
					srand((unsigned)time(0));
					random_integer = (rand()%4)+1;
					
					// if top is taken
					if (node1->northEdge != NULL
						&& node1->westEdge != NULL
						&& node1->southEdge != NULL
						&& node1->eastEdge != NULL) {
						nodesWithNoFreeEdges.push_back(node1);
						nodesWithEdges.erase(nodesWithEdges.begin() + (random_integer - 1));
					}
					if (random_integer == 1 && node1->northEdge != NULL) {
						random_integer++;
					}
					if (random_integer == 2 && node1->westEdge != NULL) {
						random_integer++;
					}
					if (random_integer == 3 && node1->southEdge != NULL) {
						random_integer++;
					}
					
					switch (random_integer) {
						case 1:
							// try the node to the top
							if (node1->row != 0
									&& (nodes[node1->row-1][node1->col])->southEdge == NULL) {
								node2 = nodes[node1->row-1][node1->col];
								
								edges[ii]->node1 = node1;
								edges[ii]->node2 = node2;
								pickedTwoNodes = true;
								if (!contains(nodesWithEdges, node2)) {
									nodesWithEdges.push_back(node2);
								}
								
								node1->northEdge = edges[ii];
								node2->southEdge = edges[ii];
							}
							break;
						case 2:
							// try the node to the left
							if (node1->col != 0
								&& (nodes[node1->row][node1->col-1])->eastEdge == NULL) {
								node2 = nodes[node1->row][node1->col-1];
								
								edges[ii]->node1 = node1;
								edges[ii]->node2 = node2;
								pickedTwoNodes = true;
								if (!contains(nodesWithEdges, node2)) {
									nodesWithEdges.push_back(node2);
								}
								
								node1->westEdge = edges[ii];
								node2->eastEdge = edges[ii];
							}
							break;
						case 3:
							// try the node to the bottom
							if (node1->row != MAP_ROWS - 1
								&& (nodes[node1->row+1][node1->col])->northEdge == NULL) {
								node2 = nodes[node1->row+1][node1->col];
								
								edges[ii]->node1 = node1;
								edges[ii]->node2 = node2;
								pickedTwoNodes = true;
								if (!contains(nodesWithEdges, node2)) {
									nodesWithEdges.push_back(node2);
								}
								
								node1->southEdge = edges[ii];
								node2->northEdge = edges[ii];
							}
							break;
						case 4:
							// try the node to the right
							if (node1->col != MAP_COLS - 1
								&& (nodes[node1->row][node1->col+1])->westEdge == NULL) {
								node2 = nodes[node1->row][node1->col+1];
								
								edges[ii]->node1 = node1;
								edges[ii]->node2 = node2;
								pickedTwoNodes = true;
								if (!contains(nodesWithEdges, node2)) {
									nodesWithEdges.push_back(node2);
								}
								
								node1->eastEdge = edges[ii];
								node2->westEdge = edges[ii];
							}
							break;
						default:
							node2 = NULL;
					}
				}
			}
		}
	}
	
	if (USEEXISTINGMAP) {
		int edgeNum = 0;
		for (int row = 0; row < MAP_ROWS-1; row++) {
			bool stop = false;
			for (int col = 0; col < MAP_COLS-1; col++) {
				edges[edgeNum]->node1 = nodes[row][col];
				edges[edgeNum]->node2 = nodes[row][col+1];
				
				nodes[row][col]->eastEdge = edges[edgeNum];
				nodes[row][col+1]->westEdge = edges[edgeNum];
				
				edgeNum++;
				if (edgeNum == MAP_EDGES) {
					stop = true;
					break;
				}
				
				edges[edgeNum]->node1 = nodes[row][col];
				edges[edgeNum]->node2 = nodes[row+1][col];
				
				nodes[row][col]->southEdge = edges[edgeNum];
				nodes[row+1][col]->northEdge = edges[edgeNum];
				
				edgeNum++;
				if (edgeNum == MAP_EDGES) {
					stop = true;
					break;
				}
			}
			if (stop) {
				break;
			}
		}
	}
	
	return;
	
	// create the adjacency matrix
	//int adjacencyMatrix[numberOfRows*numberOfCols][numberOfRows*numberOfCols];
	
	int ** adjacencyMatrix = new int*[numberOfRows*numberOfCols + 1];
    for(int i = 0; i < numberOfRows*numberOfCols + 1; i++)
		adjacencyMatrix[i] = new int[numberOfRows*numberOfCols + 1];
	
	for (int row = 1; row <= numberOfRows*numberOfCols; row++) {
		//cout << row << ")";
		int actualRow = row - 1;
		
		int node1Row = actualRow / numberOfRows;
		int node1Col = actualRow % numberOfRows;
		//cout << " (" << node1Row << " " << node1Col << ")";
		
		Node* node1 = nodes[node1Row][node1Col];
		for (int col = 1; col <= numberOfRows*numberOfCols; col++) {
			int actualCol = col - 1;
			
			int node2Row = actualCol / numberOfRows;
			int node2Col = actualCol % numberOfRows;
			Node* node2 = nodes[node2Row][node2Col];
			
			if (connected(node1, node2)) {
				adjacencyMatrix[row][col] = 10;
				//cout << 10 << " (" << node2Row << " " << node2Col << ")";
			} else {
				adjacencyMatrix[row][col] = 0;
				//cout << 0 << " ";
			}
		}
		//cout << "\n";
	}
	
	/////
	
	/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
		(infinity if there is none).
	  Also assume that n is the number of vertices and edgeCost(i,i) = 0
	 */
	int n = numberOfRows*numberOfCols;
	
	int path[n + 1][n + 1];
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; n++) {
			path[i][j] = adjacencyMatrix[i][j];
			if (path[i][j] == 0) {
				path[i][j] = 32767;
			}
		}
	}
	/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
	     from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to
	     edgeCost(i,j) or infinity if there is no edge between i and j.
	  */
	
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; i <= n; j++) {
				path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
			}
		}
	}
	
    for(int i = 0; i < numberOfRows*numberOfCols + 1; i++)
		delete adjacencyMatrix[i];
	delete adjacencyMatrix;
	
	//return;
	
	/////
	
	int c=0;
	dj a;
	a.input(numberOfRows*numberOfCols, adjacencyMatrix);
	///*
	for(int i=1;i<=a.n;i++)
	{
		a.min_dist(i);
		for(int j=1;j<=a.n;j++)
		{
			if(i!=j)
			{
				if(++c==10)
				{
					//cout<<"\n\nPress any key to continue"<<endl;
					c=0;
				}
				//cout<<"From "<<i<<" to "<<j<<":"<<endl;
				//cout<<"------------"<<endl;
				
				//cout<<"Minimum distance route: ("<<i;
				//a.disp_path(j);
				//cout<<")"<<endl;
				//a.disp_dist(j);
				
				std::vector<int> returnList = a.disp_path2(i, j);
				
				shortestPaths.push_back(new ShortestPath(i, j, returnList));
			}
		}
	}
	//*/
	//////////
	
	for (int ii = 0; ii < shortestPaths.size(); ii++) {
		//cout<<"From "<<shortestPaths[ii]->start<<" to "<<shortestPaths[ii]->end<<":"<<endl;
		//cout<<"------------"<<endl;
		
		//cout<<"Minimum distance route: ("<<shortestPaths[ii]->path[0];
		
		for (int jj = 1; jj < shortestPaths[ii]->path.size(); jj++) {
			//cout << " " << shortestPaths[ii]->path[jj];
		}
		
		//a.disp_path(j);
		//cout<<")"<<endl;
	}
	
	//return;
	
	bool flag = false;
	fstream fin;
	fin.open("saved_map.txt",ios::in);
	if( fin.is_open() )
	{
		cout<<"file exists"<<endl;
		flag=true;
	}
	fin.close();
	
	if (flag == false) {
		//save it
		ofstream myfile;
		myfile.open ("saved_map.txt");
		
		for (int row = 0; row < MAP_ROWS; row++) {
			for (int col = 0; col < MAP_COLS; col++) {
				myfile << "*";
				if (col < MAP_COLS-1) {
					if ((nodes[row][col])->eastEdge != NULL) {
						myfile << "-";
					} else {
						myfile << " ";
					}
				}
			}
			myfile << "\n";
			for (int col = 0; col < MAP_COLS; col++) {
				if (row < MAP_ROWS-1) {
					if ((nodes[row][col])->southEdge != NULL) {
						myfile << "| ";
					} else {
						myfile << "  ";
					}
				}
			}
			myfile << "\n";
		}
		
		myfile.close();
	}
}

Map::~Map( ) {
	for (int row = 0; row < numberOfRows; row++) {
		for (int col = 0; col < numberOfCols; col++) {
			delete nodes[row][col];
		}
	}
	
	for (int ii = 0; ii < MAP_EDGES; ii++) {
		delete edges[ii];
	}
	
	for (int ii = 0; ii < shortestPaths.size(); ii++) {
		delete shortestPaths[ii];
	}
}

bool Map::contains(std::vector<Node*> nodesWithEdges, Node* node2) {
	for (int ii = 0; ii < nodesWithEdges.size(); ii++) {
		if (nodesWithEdges[ii]->row == node2->row &&
			nodesWithEdges[ii]->col == node2->col) {
			return true;
		}
	}
	return false;
}
/*
void Map::print() {
	for (int row = 0; row < MAP_ROWS; row++) {
		for (int col = 0; col < MAP_COLS; col++) {
			if ((nodes[row][col])->robberFlag)
				cout << "R";
			else if ((nodes[row][col])->copsFlag)
				cout << "C";
			else if ((nodes[row][col])->hideout)
				cout << "H";
			else
				cout << "*";
			if (col < MAP_COLS-1) {
				if ((nodes[row][col])->eastEdge != NULL) {
					cout << "----------";
				} else 
						cout << "          ";
			}
		}
		cout << "\n";
		for (int i = 0; i < 10; i++){
		  for (int col = 0; col < MAP_COLS; col++) {
			if (row < MAP_ROWS-1) {
				if ((nodes[row][col])->southEdge != NULL) {
						cout << "|";
				} else {
						cout << " ";
				}
			  	cout << "          ";
			}
		  }
		 cout << "\n";
		}
	}
}
*/
bool Map::connected(Node* node1, Node* node2) {
	for (int ii = 0; ii < MAP_EDGES; ii++) {
		Edge* current_edge = edges[ii];
		if (current_edge->node1 == node1 && current_edge->node2 == node2
			|| current_edge->node1 == node2 && current_edge->node2 == node1) {
			return true;
		}
	}
	return false;
}